package com.zhupf.queue;


import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhupf
 * @date 2024年12月31日 15:15
 * @Description 862. 和至少为 K 的最短子数组
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
 * <p>
 * 子数组 是数组中 连续 的一部分。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1], k = 1
 * 输出：1
 * 示例 2：
 * <p>
 * 输入：nums = [1,2], k = 4
 * 输出：-1
 * 示例 3：
 * <p>
 * 输入：nums = [2,-1,2], k = 3
 * 输出：3
 */
public class ShortestSubarray {

    public static void main(String[] args) {
        int[] nums = {-100000, -100000, -100000};
        System.out.println(shortestSubarray(nums, 1000000000));
    }

    public static int shortestSubarray(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        Deque<Integer> deque = new LinkedList<>();
        Long[] preSum = new Long[nums.length];
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum >= k && res == Integer.MAX_VALUE) {
                res = i + 1;
            }
            preSum[i] = sum;
        }
        for (int i = 0; i < preSum.length; i++) {
            while (!deque.isEmpty() && preSum[deque.peekLast()] > preSum[i]) {
                deque.pollLast();
            }
            while (!deque.isEmpty() && preSum[i] - preSum[deque.peekFirst()] >= k) {
                res = Math.min(res, i - deque.pollFirst());
            }
            deque.offerLast(i);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
